package com.mystudy.dataStructure.collections;

/**
 * @program: infoalgorithm
 * @description: 基于二分搜索树的映射
 * 因为基于二分搜素树，所以key必须是可以比较的，要实现Comparable
 * @author: zhouzhilong
 * @create: 2019-07-29 15:15
 **/
public class BSTMap<K extends Comparable, V> implements Map<K, V> {
    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size = 0;
    }

    @Override
    public void add(K key, V val) {
        root = add(root, key, val);
    }

    private Node add(Node node, K key, V val) {
        if (node == null) {
            size++;
            return new Node(key, val);
        }
        if (node.key.compareTo(key) > 0) {
            node.left = add(node.left, key, val);
        } else if (node.key.compareTo(key) < 0) {
            node.right = add(node.right, key, val);
        } else {
            //与二叉搜索树有所不同，这里需要更新数据
            node.val = val;
        }
        return node;
    }

    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (node.key.compareTo(key) > 0) {
            return getNode(node.left, key);
        } else if (node.key.compareTo(key) < 0) {
            return getNode(node.right, key);
        } else {
            return node;
        }
    }

    @Override
    public V remove(K key) {
        Node result = getNode(root, key);
        if (result != null) {
            root = remove(root, key);
            return result.val;
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (node.key.compareTo(key) > 0) {
            node.left = remove(node.left, key);
        } else if (node.key.compareTo(key) < 0) {
            node.right = remove(node.right, key);
        } else {
            if (node.left == null) {
                size--;
                return node.right;
            }

            if (node.right == null) {
                size--;
                return node.left;
            }

            //找到右子树最小的节点
            //最复杂的情况，左子树与右子树都不为空,要找到合适的替代的节点
            //找到比要删除的节点大的最小节点，也就是要删除节点的右子树的最小节点
            Node successor = miniMum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;//解除内存占用
            return successor;
        }
        return node;
    }

    private Node miniMum(Node node) {
        if (node.left == null) {
            return node;
        } else {
            return miniMum(node.left);
        }
    }

    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;//解除内存占用
            size--;
            return rightNode;
        } else {
            node.left = removeMin(node.left);
            return node;
        }
    }

    @Override
    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    @Override
    public V get(K key) {
        Node result = getNode(root, key);
        return result == null ? null : result.val;
    }

    @Override
    public void set(K key, V val) {
        Node result = getNode(root, key);
        if (result != null) {
            result.val = val;
        } else {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        generateBSTString(root, 0, result);
        return result.toString();
    }

    /**
     * 生成以node为根节点，深度为depth的描述二叉树的字符串
     *
     * @param node   要遍历的根节点
     * @param depth  该根节点所在深度
     * @param result 最终生成的结果
     */
    private void generateBSTString(Node node, int depth, StringBuilder result) {
        if (node == null) {
            result.append(generateDepthString(depth) + "null\n");
            return;
        }
        result.append(generateDepthString(depth) + node.val + "\n");
        generateBSTString(node.left, depth + 1, result);
        generateBSTString(node.right, depth + 1, result);

    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }


    public class Node {
        public K key;
        public V val;
        public Node left;
        public Node right;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

}
